/*
 * Created on 21 mars 2005 by Tudor.Ionescu@supelec.fr
 */
package clustering.implementations;
import clustering.framework.*;
import clustering.testing.ClusteringMain;
import clustering.testing.Debug;

import java.io.File;
import java.io.FileOutputStream;
import java.util.*;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;

import org.w3c.dom.Document;
import org.w3c.dom.Node;

/**
 * @author Tudor.Ionescu@supelec.fr

VCQMTreeConstructor

This class is an implementation of the Vitanyi-Cilibrasi quartet method (VCQM). 

 */
public class RandomTreeConstructor implements IClusterTreeConstructor{
    QNode [] qNodes = null;
    int last_operation = -1;
    Hashtable htPath = new Hashtable();
    public String [] filesList = null;
    public int K = 2000;
    QuartetTree constructFromXmlDocument(Document xmlTree, QNode [] qNodes){
        QuartetTree qt = new QuartetTree();
        QNode qn = new QNode(-1,null,null,null,-1);
        Node xmlNode = xmlTree.getFirstChild();
        node_count = 0;
        for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
			generateTree(xmlNode.getChildNodes().item(i),qn,qNodes);
		}
        if(xmlNode.getChildNodes().getLength()==2){
		    QNode n1 = qn.adj[0];
		    QNode n2 = qn.adj[1];
		    n1.adj[0] = n2;
		    n2.adj[0] = n1;
		    qt.root = n1;
		}else{
		    qNodes[node_count++]=qn;
		    qt.root = qn;
		}        
        return qt;
    }
    void generateTree(Node xmlNode, QNode n0, QNode [] qNodes){
        String sId = xmlNode.getAttributes().getNamedItem("id").getNodeValue();
		int id = Integer.parseInt(sId);
		QNode qn = new QNode(id,n0,null,null,-1);
		if(n0.adj[0]==null)n0.adj[0]=qn;
		else if(n0.adj[1]==null)n0.adj[1]=qn;
		else n0.adj[2]=qn;
		if(xmlNode.hasChildNodes()){
			for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
				generateTree(xmlNode.getChildNodes().item(i),qn,qNodes);
			}			
		}
		qNodes[node_count++]=qn;
	}
    public String ConstructXMLTree(double [][] dDistanceMatrix)throws Exception{
    	qNodes = new QNode[2*dDistanceMatrix.length - 2];
    	
    	/* Start of MCQP stuff */
    	//MCQPTreeConstructor tc = new MCQPTreeConstructor();
    	//tc.K = 1;
    	//Document tree = getTree(tc,dDistanceMatrix);
    	//QuartetTree qt = constructFromXmlDocument(tree);
    	/* End of MCQP stuff */
    	
    	QuartetTree qt = createInitialTree(dDistanceMatrix.length);
        System.out.println("tree: " + qt.toTreeFile());
        
        ArrayList alQuartets = Quartet.generateFullQuartetList(dDistanceMatrix);
        qt.M = Quartet.worst_cost.doubleValue();
        qt.m = Quartet.best_cost.doubleValue();
        double score = 0;
        QNode [] qNodesOld = qNodes;
        qNodes = cloneQuartetNodes(qNodesOld,qt);
        
        /* Start of MCQP stuff */
        //QuartetTreeScorer qts = new QuartetTreeScorer();
        //double old_score = qts.ComputeScore(tree,dDistanceMatrix);
        /* End of MCQP stuff */
        
        double old_score = 0;
        double Pt_old = Double.MAX_VALUE;
        int step = 0;
        
        double sqrt_n = Math.round(Math.sqrt(dDistanceMatrix.length));
        double log_n = Math.round(Math.log(dDistanceMatrix.length));
        int stop_steps = K;
        int stop_count = 0;
        Debug.append("STOP STEPS = "+stop_steps);
        int part_q = 0;
        int non_part_q = 0;
        
        while(stop_count <= stop_steps){
            double Ct = 0;
            double Pt = 0;
            int K = 1;
            stop_count++;
            while(K < 500){
            	K++;
            	Arrays.sort(qNodes);
            	performRandomMutation(qt);
            }
            
            int consistent = 0;
            htPath.clear();

            
            boolean foundSuitableEdge = false;
            TreeEdge rootEdge = null;
            while(!foundSuitableEdge){
            	QNode qn1 = getRandomInternNode();
            	for(int i=0;i<qn1.adj.length;i++){
            		if(qn1.adj[i].id == -1){
            			rootEdge = new TreeEdge(qn1,qn1.adj[i]);
            			foundSuitableEdge = true;
            			break;
            		}
            	}
            }
	    	//qNodesOld = cloneQuartetNodes(qNodes,qt);
			step++;
            if(step % 100 == 0){
            	//Debug.append("score=" + score + "; old_score=" + old_score + "; step=" + step + " K="+K);
            	System.out.println("score=" + score + "; old_score=" + old_score + "; step=" + step + " K="+K);
            }
        }
        Debug.append("part_q = "+part_q);
        Debug.append("non_part_q = "+non_part_q);
        qt.St = old_score;
        qt.root = getRandomInternNode();
        File f = new File("test.tree");
        FileOutputStream fos = new FileOutputStream(f);
        fos.write(qt.toTreeFile().getBytes());
        fos.close();
        return qt.toString();
    }
    
    boolean equalTrees(QNode [] old_list, QNode [] new_list){
    	int i1, i2;
    	for(int i=0;i<old_list.length;i++){
    		i1 = getNodeIndex(old_list[i],old_list);
    		i2 = getNodeIndex(new_list[i],new_list);
    		if(i1 != i2)return false;
    		for(int j=0;j<old_list[i].adj.length;j++){
    			i1 = getNodeIndex(old_list[i].adj[j],old_list);
    			i2 = getNodeIndex(new_list[i].adj[j],new_list);
    			if(i1 != i2)return false;
    		}
    	}
    	return true;
    }
    
    int getNodeIndex(QNode qn, QNode [] nodesList){
    	for(int i=0;i<nodesList.length;i++){
    		if(nodesList[i]==qn)return i;
    	}
    	return -1;
    }
    
    QNode [] cloneQuartetNodes(QNode [] listNodes, QuartetTree qt){
    	QNode [] newNodes = new QNode[listNodes.length];
    	for(int i=0;i<newNodes.length;i++)newNodes[i] = new QNode(-1,null,null,null,-1);
    	for(int i=0;i<listNodes.length;i++){
    		newNodes[i].label = listNodes[i].label;
    		for(int j=0;j<newNodes[i].adj.length;j++){
    		    int index = getNodeIndex(listNodes[i].adj[j],listNodes);
    		    if(index != -1)newNodes[i].adj[j] = newNodes[index];
    		}
    	}
    	qt.root = getRandomInternNode();
    	return newNodes;
    }
    /*
    boolean isConsistent(Quartet q, QuartetTree qt){
        QNode a = getNodeByLabel(q.nodes[0]);
        QNode b = getNodeByLabel(q.nodes[1]);
        QNode c = getNodeByLabel(q.nodes[2]);
        QNode d = getNodeByLabel(q.nodes[3]);
        if(htPath.get(a)==null){
        	htPath.put(a,qt.Dijkstra(a,qNodes));
        }
        if(htPath.get(b)==null){
        	htPath.put(b,qt.Dijkstra(b,qNodes));
        }
        if(htPath.get(c)==null){
        	htPath.put(c,qt.Dijkstra(c,qNodes));
        }
        if(htPath.get(d)==null){
        	htPath.put(d,qt.Dijkstra(d,qNodes));
        }
        ArrayList path1 = (ArrayList)((Hashtable)htPath.get(a)).get(b);
        ArrayList path2 = (ArrayList)((Hashtable)htPath.get(c)).get(d);
        for(int i=1;i<path1.size()-1;i++){
            QNode qn1 = (QNode)path1.get(i);
            for(int j=1;j<path2.size()-1;j++){
                QNode qn2 = (QNode)path2.get(j);
                if(qn1 == qn2)return false;
            }
        }
        return true;
    }*/
    
    void copyPartTables(double [][] dm){
    	oldPartTable = new int[dm.length][dm.length];
    	for(int i=0;i<partTable.length;i++){
    		for(int j=0;j<partTable.length;j++){
    			oldPartTable[i][j] = partTable[i][j];
    		}
    	}
    }
    int comparePartTables(){
    	for(int k=0;k<partTable.length;k++){
    		int count = 0;
    		for(int i=0;i<partTable.length;i++){
    			if(partTable[i][k]==oldPartTable[i][k])count++;
    		}
    		if(count < partTable.length){
    			return k;
    		}
    	}
    	return partTable.length;
    }
    
    int partK = -1;
    int [][] oldPartTable = null;
    
    int [][] partTable = null;
    long operation_count = 0;
	 boolean isConsistent(Quartet q){
		 boolean nonDetermination = true;
		 boolean consistent = false;
		 int k = 0;
		 int a = q.nodes[0];
		 int b = q.nodes[1];
		 int c = q.nodes[2];
		 int d = q.nodes[3];
		 int [][] pt = partTable;
		 int [] sum = new int[4];
		 boolean nd1 = false;
		 boolean nd2 = false;
		 while(nonDetermination){
			 operation_count++;
			 sum[0] += pt[a][k];
			 sum[1] += pt[b][k];
			 sum[2] += pt[c][k];
			 sum[3] += pt[d][k];
			 //if(pt[a][k]==pt[b][k] && pt[c][k]==pt[d][k] && pt[a][k]!=pt[c][k]){
			 if(sum[0]==sum[1] && sum[2]==sum[3] && sum[0]!=sum[2]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(pt[a][k]!=pt[b][k] && pt[c][k]!=pt[d][k]){
			 //}else if(sum[0]!=sum[1] && sum[2]!=sum[3]){
				 nonDetermination = false;
				 consistent = false;
			 }else if(sum[2]==sum[3] && sum[2]!=sum[0] && sum[2]!=sum[1]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(pt[c][k]==pt[d][k] && pt[c][k]!=pt[a][k] && pt[c][k]!=pt[b][k]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(sum[0]==sum[1] && sum[0]!=sum[2] && sum[0]!=sum[3]){
				 nonDetermination = false;
				 consistent = true;
			 }else if(pt[a][k]==pt[b][k] && pt[a][k]!=pt[c][k] && pt[a][k]!=pt[d][k]){
				 nonDetermination = false;
				 consistent = true;
			 }else if((pt[a][k]==0 && pt[b][k]==0)||(pt[c][k]==0 && pt[d][k]==0)){
				 nonDetermination = false;
				 consistent = true;
			 }else{
				 if((pt[a][k]!=pt[b][k])){
					 nd1 = true;
					 sum[2] = 0;
					 sum[3] = 0;
					 if(pt[a][k]==pt[c][k]){
						 sum[0]=0;
					 }else{
						 sum[1]=0;
					 }
				 }
				 if((pt[c][k]!=pt[d][k])){
					 nd2 = true;
					 sum[0]=0;
					 sum[1]=0;
					 if(pt[c][k]==pt[a][k]){
						 sum[2]=0;
					 }else{
						 sum[3]=0;
					 }
				 }
				 if(nd1 && nd2){
					 nonDetermination = false;
					 consistent = false;
				 }
			 }
			 k++;
		 }
		 q.consistent = consistent;
		 q.K = k;
		 return consistent;
	 }
	 
	 void partitionTree(QuartetTree qt, TreeEdge te, int n){
		 partTable = new int[n][n];
		 int [] partList = new int[n];
		 partList[0]=1;
		 biPart(te.q1,te.q2,partList,0);
		 partList[0]=2;
		 biPart(te.q2,te.q1,partList,0);
	 }
	 void biPart(QNode qn, QNode parent, int [] partList, int depth){
		 if(qn.label != -1){
			 for(int i=0;i<depth;i++){
				 partTable[qn.label][i] = partList[i];
			 }
			 return;
		 }
		 boolean first = true;
		 boolean leaf = false;
		 for(int i=0;i<qn.adj.length;i++){
			 if(qn.adj[i]!=parent){
				 if(first){
					 partList[depth+1]=1;
					 biPart(qn.adj[i],qn,partList,depth+1);
					 first = false;
					 if(qn.adj[i].label != -1)leaf = true;
				 }else{
					 if(leaf){
						 partList[depth+1]=1;
					 }else{
						 partList[depth+1]=2;
					 }
					 biPart(qn.adj[i],qn,partList,depth+1); 
				 }				 
			 }
		 }
	 }
    
    QNode getNodeByLabel(int label){
        for(int i=0;i<qNodes.length;i++){
            QNode qn = qNodes[i];
            if(qn.label == label)return qn;
        }
        return null;
    }

      
    void performRandomMutation(QuartetTree qt)throws Exception{
    	int operation = rand.nextInt(6);
        last_operation = operation;
        QNode n1 = null, n2 = null;
        if(operation == 0 || operation == 1){
        
        	if(operation == 0){ // leaf swap
        	    n1 = getRandomLeafNode();
        	    n2 = getRandomLeafNode();
        		while(n1.adj[0] == n2.adj[0]){
        			n1 = getRandomLeafNode();
        			n2 = getRandomLeafNode();
        		}
        		// just exchange their labels
        		int temp_label = n1.label;
        		n1.label = n2.label;
        		n2.label = temp_label;
            }else{ // subtree swap
                n1 = getRandomInternNode();
                n2 = getRandomInternNode();
        	    ArrayList path = qt.Dijkstra(n2,n1,qNodes);
        	    
        	    // make sure the path has more than 3 nodes, including n1 and n2
                while(path.size() <= 3){
                	n1 = getRandomInternNode();
                	n2 = getRandomInternNode();
                	path = qt.Dijkstra(n2,n1,qNodes);
            	}

                // exchange the adjacent nodes
                QNode bucket = n1.adj[n1.getAdjIndex((QNode)path.get(1))];
                n1.adj[n1.getAdjIndex((QNode)path.get(1))] = n2.adj[n2.getAdjIndex((QNode)path.get(path.size()-2))];
                n2.adj[n2.getAdjIndex((QNode)path.get(path.size()-2))] = bucket;
                
                // update their referers
                QNode n1_adj = (QNode)path.get(1);
                n1_adj.adj[n1_adj.getAdjIndex(n1)] = n2;
                QNode n2_adj = (QNode)path.get(path.size()-2);
                n2_adj.adj[n2_adj.getAdjIndex(n2)] = n1;
            }        	        	
        }else{ // subtree transfer
            n1 = getRandomNode();
            n2 = getRandomNode();
            ArrayList path = qt.Dijkstra(n2,n1,qNodes);
            
        	while(path.size() <= 3){
        	    n1 = getRandomNode();
        	    n2 = getRandomNode();
                path = qt.Dijkstra(n2,n1,qNodes);
    		}
        	
        	// --- begin of disconnect ---
        	// the node to be transfered
        	QNode tn = (QNode)path.get(path.size()-2);
        	// this is the next node after tn from the path from n2 to n1
        	QNode n3 = (QNode)path.get(path.size() - 3);
        	// the node to be shifted
        	QNode shift = tn.adj[tn.getThirdAdjIndex(n3,n2)];
        	
        	n3.adj[n3.getAdjIndex(tn)] = shift;
        	shift.adj[shift.getAdjIndex(tn)] = n3;
        	// --- end of disconnect ---
        	
        	// --- begin of connect ---
        	QNode n4 = (QNode)path.get(1);
        	n1.adj[n1.getAdjIndex(n4)] = tn;
        	
        	int i1 = rand.nextInt(2);
        	int i2 = (i1 + 1)%3;
        	int i3 = (i2 + 1)%3;
        	
        	tn.adj[i1] = n1;
        	tn.adj[i2] = n2;
        	n4.adj[n4.getAdjIndex(n1)] = tn;
        	tn.adj[i3] = n4;
        	// --- end of connect --
        	
        }
	}
    
	Random rand = new Random();
    QNode getRandomNode(){
        int k = rand.nextInt(qNodes.length);
        return qNodes[k];
    }
    QNode getRandomLeafNode(){
        QNode qn = getRandomNode();
        while(qn.label == -1)qn = getRandomNode();
        return qn;
    }
    QNode getRandomInternNode(){
        QNode qn = getRandomNode();
        while(qn.label != -1)qn = getRandomNode();
        return qn;
    }
    
    
    // creates the initial quartet tree
    
    QuartetTree createInitialTree(int n){
        QuartetTree qt = new QuartetTree();
        node_count = 0; 
        for(int i=0;i<3;i++)qt.root.adj[i] = new QNode(-1,qt.root,null,null,-1);
        addNodePair(qt.root.adj[0],0,n/3);
        addNodePair(qt.root.adj[1],n/3,2*n/3);
        addNodePair(qt.root.adj[2],2*n/3,n);
        qNodes[node_count] = qt.root;
        qt.N = n;
        return qt;
    }
    
    // counter for the number of nodes to be added in the list of nodes
    int node_count = 0;
    
    // creates new nodes for second - qn.adj[1] - and third neighbor - qn.adj[2]
    // the first neighbor - qn.adj[0] - is the link to the referer node
    void addNodePair(QNode qn, int k, int n){
        qNodes[node_count++] = qn;
        if(k >= n)return;
        
        qn.adj[1] = new QNode(k,qn,null,null,-1);
        qNodes[node_count++] = qn.adj[1];
        if(n - k >= 3){
            qn.adj[2] = new QNode(-1,qn,null,null,-1);
            addNodePair(qn.adj[2],k+1,n);
        }else{
            qn.adj[2] = new QNode(k+1,qn,null,null,-1);
            addNodePair(qn.adj[2],k+2,n);
        }       
    }
    
    //int node_count;
    QuartetTree constructFromXmlDocument(Document xmlTree){
        QuartetTree qt = new QuartetTree();
        QNode qn = new QNode(-1,null,null,null);
        Node xmlNode = xmlTree.getFirstChild();
        node_count = 0;
        for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
			generateTree(xmlNode.getChildNodes().item(i),qn);
		}
        if(xmlNode.getChildNodes().getLength()==2){
		    QNode n1 = qn.adj[0];
		    QNode n2 = qn.adj[1];
		    n1.adj[0] = n2;
		    n2.adj[0] = n1;
		    qt.root = n1;
		}else{
		    qNodes[node_count++]=qn;
		    qt.root = qn;
		}        
        return qt;
    }
    void generateTree(Node xmlNode, QNode n0){
        String sId = xmlNode.getAttributes().getNamedItem("id").getNodeValue();
		int id = Integer.parseInt(sId);
		QNode qn = new QNode(id,n0,null,null);
		if(n0.adj[0]==null)n0.adj[0]=qn;
		else if(n0.adj[1]==null)n0.adj[1]=qn;
		else n0.adj[2]=qn;
		if(xmlNode.hasChildNodes()){
			for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
				generateTree(xmlNode.getChildNodes().item(i),qn);
			}			
		}
		qNodes[node_count++]=qn;
	}
    Document getTree(IClusterTreeConstructor utc, double [][] dMatrix)throws Exception{
	    String xmlTree = utc.ConstructXMLTree(dMatrix);
		
		FileOutputStream fos = new FileOutputStream("test.xml");
		fos.write(xmlTree.getBytes());
		fos.close();
		
		DocumentBuilderFactory docbuilderfact = DocumentBuilderFactory.newInstance();
		DocumentBuilder docbuilder = docbuilderfact.newDocumentBuilder();
		File f = new File("test.xml");
		//File f = new File("c:\\temp\\lang\\tree_87.txt");
		return docbuilder.parse(f);
	}
    
}